package 牛客算法篇;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-02-27
 * Time:19:37
 */

/**
 * 牛客算法篇:BM16 删除有序链表中重复的元素-II
 通过率：30.86% 时间限制：1秒
 空间限制：256M
 知识点
 链表
 描述
 给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
 例如：
 给出的链表为1→2→3→3→4→4→51→2→3→3→4→4→5, 返回1→2→51→2→5.
 给出的链表为1→1→1→2→31→1→1→2→3, 返回2→32→3.
 数据范围：链表长度 0≤n≤100000≤n≤10000，链表中的值满足 ∣val∣≤1000∣val∣≤1000
 要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
 示例1
 输入：
 {1,2,2}
 返回值：
 {1}
 */
public class deleteDuplicatesⅡ {
    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(1);
        ListNode c = new ListNode(1);
//        ListNode c = new ListNode(3);
//        ListNode d = new ListNode(2);
//        ListNode e = new ListNode(1);

        a.next = b;
        b.next = c;
//        c.next = d;
//        d.next = e;
        deleteDuplicates(a);

    }
    public static ListNode deleteDuplicates (ListNode head) {
        // write code here
        if(head == null || head.next == null){
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = head;
        ListNode pre = dummy;

        while(cur != null){
            boolean isok = false;
            while(cur.next != null && cur.val == cur.next.val){
                isok = true;
                cur = cur.next;
            }
            if(isok){
                pre.next = cur.next;
            }else{
                pre = cur;
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}
